/LMAR=0/XLINE=3/FONT#0=BAXL30[FNT,CLT]/FONT#1=BAXM30/FONT#2=BAXB30[FNT,CLT]/FONT#5=GACS25/FONT#3=SUB/FONT#4=SUP/FONT#7=SYMB30[FNT,CLT]

␈↓ ↓H␈↓␈↓ ¬πSTANFORD UNIVERSITY

␈↓ ↓H␈↓CS206  ␈↓ βZCOMPUTING WITH SYMBOLIC EXPRESSIONS  ␈↓ 
0FALL 1978

␈↓ ↓H␈↓␈↓ ¬DPROBLEM SET  1
␈↓ ↓H␈↓␈↓ ¬[Due  October 24

␈↓ ↓H␈↓        Write␈αLISP␈αprograms␈αfor␈αeach␈αof␈αthe␈α
functions␈αdescribed␈αbelow.␈α For␈αeach␈αprogram␈αturn␈α
in
␈↓ ↓H␈↓the following:

␈↓ ↓H␈↓␈↓ βλ1.  The internal form of the program.
␈↓ ↓H␈↓␈↓ βλ2.  The corresponding external form recursive definition.
␈↓ ↓H␈↓␈↓ βλ3.  A description of how the progam works and why.
␈↓ ↓H␈↓␈↓ βλ4.  Output from test runs on a variety of input.

␈↓ ↓H␈↓        Late assignments are discouraged and will not be accepted after the solutions appear.


␈↓ ↓H␈↓αFunction descriptions.

␈↓ ↓H␈↓1.␈α⊂␈↓↓sizesort[u]␈↓␈α⊂returns␈α∂a␈α⊂permutation␈α⊂of␈α⊂␈↓↓u␈↓␈α∂which␈α⊂has␈α⊂smaller␈α∂length␈α⊂sublists␈α⊂before␈α⊂larger␈α∂ones.
␈↓ ↓H␈↓␈↓ α(Atomic␈αelements␈α
should␈αbe␈αconsidered␈α
to␈αhave␈α0␈α
length.␈α Sublists␈αof␈α
the␈αsame␈αsize␈α
can␈αbe
␈↓ ↓H␈↓␈↓ α(in any order.  The following is one i/o pair which satisfies the function definition.

␈↓ ↓H␈↓␈↓ αG␈↓↓sizesort[␈↓¬(H (D E) (F G H) (D F) B A)␈↓↓] = ␈↓¬(H B A (D E) (D F) (F G H))␈↓↓.␈↓ 

␈↓ ↓H␈↓2.␈α
␈↓↓powerset[u]␈↓␈α
returns␈α
the␈α
power-set␈α
of␈α
set␈α
␈↓↓u.␈↓␈α
 A␈α
set␈α
is␈α
represented␈α
as␈α
a␈α
list␈α
of␈α
elements␈α
with␈α
no
␈↓ ↓H␈↓␈↓ α(repetitions.␈α⊂Order␈α⊂within␈α∂the␈α⊂list␈α⊂is␈α∂unimportant.␈α⊂ The␈α⊂following␈α∂is␈α⊂one␈α⊂i/o␈α⊂pair␈α∂which
␈↓ ↓H␈↓␈↓ α(satisfies the function definition.

␈↓ ↓H␈↓␈↓ αg␈↓↓powerset[␈↓¬(A B C)␈↓↓] = ␈↓¬((A B C) (A B) (A C) (A) (B C) (B) (C) ())␈↓↓.␈↓ 

␈↓ ↓H␈↓3.␈α∂␈↓↓allsub[u,v]␈↓␈α⊂returns␈α∂a␈α⊂list␈α∂giving␈α⊂all␈α∂occurrences␈α⊂of␈α∂the␈α∂list␈α⊂␈↓↓u␈↓␈α∂as␈α⊂a␈α∂toplevel␈α⊂sublist␈α∂of␈α⊂␈↓↓v.␈↓␈α∂An
␈↓ ↓H␈↓␈↓ α(occurrence␈α∂is␈α∂given␈α∂by␈α∂the␈α∂number␈α∂denoting␈α∂the␈α∂position␈α∂in␈α∂␈↓↓v␈↓␈α∂where␈α∂the␈α∂match␈α∂begins.
␈↓ ↓H␈↓␈↓ α(The following is one i/o pair which satisfies the function definition.

␈↓ ↓H␈↓␈↓ ∧0␈↓↓allsub[␈↓¬(A A),(A A A A A)␈↓↓] = ␈↓¬(1 2 3 4)␈↓↓.␈↓ 

␈↓ ↓H␈↓4.␈α
␈↓↓allsub![u,v]␈↓␈α
returns␈α
a␈αlist␈α
giving␈α
all␈α
occurrences␈α
of␈αthe␈α
list␈α
␈↓↓u␈↓␈α
as␈α
a␈αsublist␈α
of␈α
␈↓↓v,␈↓␈α
at␈α
any␈αlevel.␈α
 Now
␈↓ ↓H␈↓␈↓ α(an␈αoccurrence␈αis␈αa␈αlist␈αof␈αnumbers␈αgiving␈αthe␈αpath␈αto␈αbeginning␈αto␈αsublist␈αoccurrence.␈αThe
␈↓ ↓H␈↓␈↓ α(following is one i/o pair which satisfies the function definition.

␈↓ ↓H␈↓␈↓ β∧␈↓↓allsub![␈↓¬(A),(A (B (A (B (A)))))␈↓↓] = ␈↓¬((1) (2 2 1) (2 2 2 2 1))␈↓↓␈↓ 

␈↓ ↓H␈↓5.␈α ␈↓↓mapexp␈↓␈αtakes␈αas␈αarguments␈α
an␈αS-expression,␈αa␈αunary␈αfunction␈α
␈↓↓f1␈↓␈αand␈αa␈αbinary␈αfunction␈α␈↓↓f2.␈↓␈α
 It
␈↓ ↓H␈↓␈↓ α(takes␈αthe␈αS-expression␈αapart,␈αapplies␈αthe␈α
unary␈αfunction␈αto␈αeach␈αatom␈αand␈αputs␈α
the␈αresult
␈↓ ↓H␈↓␈↓ α(back␈αtogether␈αusing␈αthe␈αbinary␈αfunction␈αThus␈αif␈α␈↓↓f1␈↓␈αis␈αthe␈αidentity␈αfunction␈αand␈α␈↓↓f2␈↓␈αis␈α␈↓↓cons␈↓
␈↓ ↓H␈↓␈↓ α(then␈α⊃␈↓↓maptree␈↓␈α⊃returns␈α⊃a␈α⊃copy␈α⊃of␈α⊃the␈α⊃S-expression.␈α⊃ If␈α⊃␈↓↓f1␈↓␈α⊃is␈α⊃␈↓↓ncons␈↓␈α⊃(forms␈α⊃a␈α⊃list␈α⊃of␈α⊂one
␈↓ ↓H␈↓␈↓ α(element) and ␈↓↓f2␈↓ is ␈↓↓append␈↓ then ␈↓↓maptree␈↓ returns the ␈↓↓fringe␈↓ of the S-expression.

␈↓ ↓H␈↓6.␈α Let␈αa␈α
graph␈α␈↓↓g␈↓␈αbe␈αrepresented␈α
as␈αdescribed␈αin␈α
Chapter␈αI␈αof␈αthe␈α
text␈αand␈αsuppose␈αthat␈α
whenever
␈↓ ↓H␈↓␈↓ α(there␈α
is␈αan␈α
edge␈α
from␈α␈↓↓x␈↓␈α
to␈α␈↓↓y␈↓␈α
 there␈α
is␈αalso␈α
an␈α
edge␈αfrom␈α
␈↓↓y␈↓␈αto␈α
␈↓↓x.␈↓␈α
 A␈αcomponent␈α
of␈αthe␈α
graph
␈↓ ↓H␈↓␈↓ α(is␈α∂a␈α∂collection␈α∂of␈α∂vertices␈α⊂which␈α∂are␈α∂all␈α∂connected␈α∂to␈α⊂each␈α∂other␈α∂by␈α∂edge␈α∂paths␈α⊂but␈α∂not
␈↓ ↓H␈↓␈↓ α(connected␈αto␈αany␈αvertices␈αnot␈αin␈αthis␈αcollection.␈α Write␈αa␈αfunction␈α␈↓↓components␈↓␈αto␈αdetermine
␈↓ ↓H␈↓␈↓ α(the components of a graph ␈↓↓g.␈↓
␈↓ ↓H␈↓␈↓ ∧+COMPUTER SCIENCE DEPARTMENT␈↓ ↓H␈↓␈↓ εH␈↓ 91
␈↓ ↓H␈↓␈↓ ¬πSTANFORD UNIVERSITY

␈↓ ↓H␈↓CS206  ␈↓ βZCOMPUTING WITH SYMBOLIC EXPRESSIONS  ␈↓ 
0FALL 1978


␈↓ ↓H␈↓α␈↓ αzFunctions definitions (external and internal form) for assignment 1.

␈↓ ↓H␈↓1. ␈↓↓sizesort[u]␈↓

␈↓ ↓H␈↓↓        sizesort[u] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ addtolist[␈↓αa|␈↓↓u, sizesort[␈↓αd|␈↓↓u]]

␈↓ ↓H␈↓↓        addtolist[x,v] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αn|␈↓↓v ␈↓αthen␈↓↓ <x>
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓if len[x] < len[␈↓αa|␈↓↓v] ␈↓αthen␈↓↓ x . v
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ ␈↓αa|␈↓↓v . addtolist[x,␈↓αd|␈↓↓v]

␈↓ ↓H␈↓↓        len[w] ←
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αat|␈↓↓w ␈↓αthen␈↓↓ 0 ␈↓αelse␈↓↓ 1 + len[␈↓αd|␈↓↓w]

␈↓ ↓H␈↓¬        (DEFUN SIZESORT(U)
␈↓ ↓H␈↓¬               (COND ((NULL U) NIL) (T (ADDTOLIST (CAR U) (SIZESORT (CDR U)))))

␈↓ ↓H␈↓¬        (DEFUN ADDTOLIST (X V)
␈↓ ↓H␈↓¬               (COND ((NULL V) (CONS X NIL))
␈↓ ↓H␈↓¬                     ((LESSP (LEN X) (LEN (CAR V))) (CONS X V))
␈↓ ↓H␈↓¬                     (T (CONS (CAR V) (ADDTOLIST X (CDR V))))))

␈↓ ↓H␈↓¬        (DEFUN LEN (W) (COND ((ATOM W) 0) (T (ADD1 (LEN (CDR W))))))

␈↓ ↓H␈↓2. ␈↓↓powerset[u]␈↓

␈↓ ↓H␈↓↓        powerset[u] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ <␈↓¬NIL␈↓↓>
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ addfront[␈↓αa|␈↓↓u,powerset[␈↓αd|␈↓↓u]]*powerset[␈↓αd|␈↓↓u]

␈↓ ↓H␈↓↓        addfront[x,v] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αn|␈↓↓v ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ [x . ␈↓αa|␈↓↓v] . addfront[x, ␈↓αd|␈↓↓v]

␈↓ ↓H␈↓¬        (DEFUN POWERSET(U)
␈↓ ↓H␈↓¬               (COND ((NULL U) (CONS NIL NIL))
␈↓ ↓H␈↓¬                     (T (APPEND (ADDFRONT (CAR U) (POWERSET (CDR U)))
␈↓ ↓H␈↓¬                                (POWERSET (CDR U))))))

␈↓ ↓H␈↓¬        (DEFUN ADDFRONT (X V)
␈↓ ↓H␈↓¬               (COND ((NULL V) NIL)
␈↓ ↓H␈↓¬                     (T (CONS (CONS X (CAR V)) (ADDFRONT X (CDR V))))))

␈↓ ↓H␈↓3. ␈↓↓allsub[u,v]␈↓

␈↓ ↓H␈↓↓        allsub[u, v] ← allsub1[u, v, 1]

␈↓ ↓H␈↓↓        allsub1[u, v, n] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αn|␈↓↓v ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ ␈↓αif␈↓↓ match[u, v] ␈↓αthen␈↓↓ n . allsub1[u, ␈↓αd|␈↓↓v, add1 n]
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ allsub1[u, ␈↓αd|␈↓↓v, add1 n]␈↓ ↓H␈↓␈↓ εH␈↓ 92

␈↓ ↓H␈↓↓        match[u, v] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ ␈↓¬T␈↓↓ ␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αn|␈↓↓v ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓ ␈↓αelse␈↓↓ ␈↓αa|␈↓↓u = ␈↓αa|␈↓↓v ∧ match[␈↓αd|␈↓↓u, ␈↓αd|␈↓↓v]

␈↓ ↓H␈↓¬        (DEFUN ALLSUB (U V) (ALLSUB1 U V 1.))

␈↓ ↓H␈↓¬        (DEFUN ALLSUB1 (U V N)
␈↓ ↓H␈↓¬               (COND ((NULL V) NIL)
␈↓ ↓H␈↓¬                     ((MATCH U V) (CONS N (ALLSUB1 U (CDR V) (ADD1 N))))
␈↓ ↓H␈↓¬                     (T (ALLSUB1 U (CDR V) (ADD1 N)))))

␈↓ ↓H␈↓¬        (DEFUN MATCH (U V)
␈↓ ↓H␈↓¬               (COND ((NULL U) T)
␈↓ ↓H␈↓¬                     ((NULL V) NIL)
␈↓ ↓H␈↓¬                     (T (AND (EQUAL (CAR U) (CAR V))
␈↓ ↓H␈↓¬                             (MATCH (CDR U) (CDR V))))))

␈↓ ↓H␈↓4. ␈↓↓allsub![u,v]␈↓

␈↓ ↓H␈↓↓        allsub![u, v] ← allsub!1[u, v, 1]

␈↓ ↓H␈↓↓        allsub!1[u, v, n] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αn|␈↓↓v ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ ␈↓αif␈↓↓ match[u, v] ␈↓αthen␈↓↓ <n> . allsub!1[u, ␈↓αd|␈↓↓v, add1 n]
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αat|␈↓↓␈↓αa|␈↓↓v ␈↓αthen␈↓↓ allsub!1[u, ␈↓αd|␈↓↓v, add1 n]
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ tack[n, allsub![u, ␈↓αa|␈↓↓v]] * allsub!1[u, ␈↓αd|␈↓↓v, add1 n]

␈↓ ↓H␈↓↓        tack[n, w] ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓w ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓ ␈↓αelse␈↓↓ [n . ␈↓αa|␈↓↓w] . tack[n, ␈↓αd|␈↓↓w]

␈↓ ↓H␈↓¬        (DEFUN ALLSUB! (U V) (ALLSUB!1 U V 1.))

␈↓ ↓H␈↓¬        (DEFUN ALLSUB!1 (U V N)
␈↓ ↓H␈↓¬               (COND ((NULL V) NIL)
␈↓ ↓H␈↓¬                     ((MATCH U V)
␈↓ ↓H␈↓¬                      (CONS (LIST N) (ALLSUB!1 U (CDR V) (ADD1 N))))
␈↓ ↓H␈↓¬                     ((ATOM (CAR V)) (ALLSUB!1 U (CDR V) (ADD1 N)))
␈↓ ↓H␈↓¬                     (T (APPEND (TACK N (ALLSUB! U (CAR V)))
␈↓ ↓H␈↓¬                                (ALLSUB!1 U (CDR V) (ADD1 N))))))

␈↓ ↓H␈↓¬        (DEFUN TACK (N W)
␈↓ ↓H␈↓¬               (COND ((NULL W) NIL)
␈↓ ↓H␈↓¬                     (T (CONS (CONS N (CAR W)) (TACK N (CDR W))))))

␈↓ ↓H␈↓5.  ␈↓↓mapexp␈↓ [or ␈↓↓maptree␈↓]

␈↓ ↓H␈↓↓        maptree[s, f1, f2] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αat|␈↓↓s ␈↓αthen␈↓↓ f1 s
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ f2[maptree[␈↓αa|␈↓↓s, f1, f2], maptree[␈↓αd|␈↓↓s, f1, f2]]

␈↓ ↓H␈↓¬        (DEFUN MAPTREE (S F1 F2)
␈↓ ↓H␈↓¬               (COND ((ATOM S) (F1 S))
␈↓ ↓H␈↓¬                     (T (F2 (MAPTREE (CAR S) F1 F2)
␈↓ ↓H␈↓¬                            (MAPTREE (CDR S) F1 F2)))))

␈↓ ↓H␈↓6. ␈↓↓components[g]␈↓

␈↓ ↓H␈↓↓        components[g] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αn|␈↓↓g ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ peel[components1[␈↓αa|␈↓↓g, ␈↓αd|␈↓↓g, ␈↓¬NIL␈↓↓, T]]␈↓ ↓H␈↓␈↓ εH␈↓ 93

␈↓ ↓H␈↓↓        peel[x] ← [␈↓αa|␈↓↓x] . components[␈↓αd|␈↓↓x]

␈↓ ↓H␈↓↓        components1[c,l,p,flag] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αn|␈↓↓l ∧ (flag ∨ ␈↓αn|␈↓↓p) ␈↓αthen␈↓↓ c . p
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓if ␈↓αn|␈↓↓l ␈↓αthen␈↓↓ components1[c,p,␈↓¬NIL␈↓↓,T]
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓if member[␈↓αa|␈↓↓␈↓αa|␈↓↓l,c] ␈↓αthen␈↓↓ components1[c * ␈↓αa|␈↓↓l,␈↓αd|␈↓↓l,p,␈↓¬NIL␈↓↓]
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ components1[c,␈↓αd|␈↓↓l,␈↓αa|␈↓↓l . p,flag]

␈↓ ↓H␈↓¬        (DEFUN COMPONENTS (G)
␈↓ ↓H␈↓¬               (COND ((NULL G) NIL)
␈↓ ↓H␈↓¬                     (T (PEEL (COMPONENTS1 (CAR G) (CDR G) NIL T))))))

␈↓ ↓H␈↓¬        (DEFUN PEEL (X) (CONS (CAR X) (COMPONENTS (CDR X))))

␈↓ ↓H␈↓¬        (DEFUN COMPONENTS1 (C L P FLAG)
␈↓ ↓H␈↓¬                (COND ((AND (NULL L) (OR FLAG (NULL P))) (CONS C P))
␈↓ ↓H␈↓¬                      ((NULL L) (COMPONENTS C P NIL T))
␈↓ ↓H␈↓¬                      ((MEMBER (CAAR L) C)
␈↓ ↓H␈↓¬                       (COMPONENTS1 (APPEND C (CAR L)) (CDR L) P NIL))
␈↓ ↓H␈↓¬                      (T (COMPONENTS1 C (CDR L) (CONS (CAR L) P) FLAG))))